package ljl.alg.wangzheng_camp.round1.slidingwindow;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 很好又发现了不会的
 * */
public class _offer48_longest_no_repeat_str {
    
    /**
     * 最长，得记个 max；只要长度，返回 max
     * map 记录每个字符的个数？
     * list 记录下标？
     *
     * 你这不是死记硬背是啥？
     *
     * 牛逼吗？改了几千次，才改对
     *
     * */
    public int lengthOfLongestSubstring1(String s) {
        if (s.length() == 0) return 0;
        Map<Character, Integer> map = new HashMap<>();
        LinkedList<Integer> indexes = new LinkedList<>();
        int n = s.length(), max = 1;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            Integer old = map.put(c, map.getOrDefault(c, 0) + 1);
            indexes.offer(i);
        
            if (old != null && old == 1) {
                char removed;
                while (!indexes.isEmpty() && s.charAt(indexes.peekFirst()) != c) {
                    removed = s.charAt(indexes.pollFirst());
                    map.put(removed, map.get(removed) - 1);
                }
            
                removed = s.charAt(indexes.pollFirst());
                map.put(removed, map.get(removed) - 1);
            
            } else {
                if (indexes.size() > max) max = indexes.size();
            }
        }
        return max;
    }
    
    /**
     * 使用一个变量记录上一次出现位置
     * 每次放完 c 之后判断上一次位置和当前距离即可
     *
     * 这里有个难点，是中间那个 if，还得求一次 max
     *
     * */
    public int lengthOfLongestSubstring(String s) {
        int old = -1, max = 0, n = s.length();
        Map<Character, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (indexMap.containsKey(c)) {
                old = Math.max(old, indexMap.get(c));
            }
            indexMap.put(c, i);
            max = Math.max(max, i - old);
        }
        return max;
    }
}
